The minmax multidimensional knapsack problem with application to a chance‐constrained problem

In this paper we present a new combinatorial problem, called minmax multidimensional knapsack problem (MKP), motivated by a military logistics problem. The logistics problem is a two‐period, two‐level, chance‐constrained problem with recourse. We show that the MKP is NP‐hard and develop a practically efficient combinatorial algorithm for solving it. We also show that under some reasonable assumptions regarding the operational setting of the logistics problem, the chance‐constrained optimization problem is decomposable into a series of MKPs that are solved separately. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

卫星在役考核相关问题研究

各类卫星在现代战争中发挥着重要和关键作用。我国传统的卫星试验和鉴定具有很强的科研试验性质,承制单位和用户重点关注的是性能检验,较少考虑作战效能和部队适用性等指标。为推动卫星装备建设和应用,装备试验鉴定部门初步组织开展了相应的在役考核工作。文章对比了美军装备作战试验与鉴定、我国作战试验与在役考核的概念;提出卫星在役考核的六大特点;分析卫星在役考核的组织方式、组织机构和组织保障的不足,提出相应发展建议;研究卫星在役考核指标体系设计、分析评估方法、问题反馈与整改等方面的不足,并提出相应措施建议。     

导弹贮存寿命预估的组合模型

在分析比较了几种寿命预估方法优缺点的基础上,针对单一预估方法在解决实际问题中所暴露的局限性,优选了GM-BPNN组合预估模型。该组合模型既利用了灰色预估理论具有所需要的样本数据少、原理简单、运算方便、短期预估精度高、可检验等优点,也发挥了神经网络并行计算、容错能力强、自适应能力强等优点。最后利用该组合模型对弹上某设备寿命进行了预估,取得了较好的预测效果。     

炮兵指挥信息系统综合训练质量评估

针对炮兵指挥信息系统综合训练质量评估的复杂性,按照"三位一体"的原则,全面考虑评估目的、被评对象特点、评估方法三者之间的协调一致性,采用了多级模糊综合评价方法与因子分析法相结合的组合评价方法,既实现了对训练质量的量化评估排序,又查找分析了影响综合训练质量的因素,经实例验证可行有效。     

Exponential size neighborhoods for makespan minimization scheduling

We investigate the quality of local search heuristics for the scheduling problem of minimizing the makespan on identical parallel machines. We study exponential size neighborhoods (whose size grows exponentially with the input length) that can be searched in polynomial time, and we derive worst‐case approximation guarantees for the local optima of such neighborhoods. The so‐called split neighborhood splits a feasible schedule into two layers, and then recombines the two layers by finding a perfect matching. We show that the makespan of every local optimum for split is at most a factor of 2 away from the globally optimal makespan. We then combine the split neighborhood with two neighborhoods from the literature. The combination of split with the jump neighborhood only marginally improves the approximation guarantee, whereas the combination with the lexicographic‐jump neighborhood decreases the approximation guarantee from 2 to 3/2. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

航空时敏制导炸弹增程弹道组合优化设计

为增强航空时敏制导炸弹在中制导段的滑翔能力,将极小值原理与自适应进化粒子群算法相结合,提出了一种适用于航空时敏制导炸弹增程弹道的组合优化设计方法。基于纵向平面内质心运动模型,推导了性能指标泛函及各不等式约束函数。引入Lagrange乘子矢量并建立相应的Hamilton函数实现无约束泛函极值问题的转换,推导出兼顾各优化目标函数的满意优化模型。利用自适应进化粒子群算法对该段增程弹道进行了攻角与弹翼张合档位双设计变量的组合优化。数值仿真算例表明,在满足状态方程约束的条件下,双变量的增程效果比常规单变量控制时显著提高,其优化结果可为制导炸弹弹道规划设计的研究提供一定的理论参考。     

基于云理论的装备技术状态预测

通过分析装备技术状态变化的模糊性和不确定性等特性,提出了基于云理论的装备技术状态预测模型.根据装备技术状态劣化趋势,给出了基于云模型的时间序列状态预测方法,有效地运用了装备状态评估中的主观预测知识.将历史趋势与当前趋势相结合,实现了基于时间序列的状态预测.最后以某装备的发动机为研究对象,对发动机状态的动态评估值进行了预测,验证了该状态预测方法的有效性.     

装备体系贡献率评估综述

随着装备体系化作战模式在军事活动中的深入运用,其表现出的优势已被世界军事强国高度关注,装备体系贡献率作为衡量装备成体系化建设与作战运用优劣程度的重要指标,已成为当前军事学术中研究的热点.系统梳理与归纳了国内外对装备体系贡献率评估需求、评估理论、评估方法的研究现状,总结出研究成果中存在的问题,为下一步开展装备体系贡献率研...     

Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost

In the last decade, there has been much progress in understanding scheduling problems in which selfish jobs aim to minimize their individual completion time. Most of this work has focused on makespan minimization as social objective. In contrast, we consider as social cost the total weighted completion time, that is, the sum of the agent costs, a standard definition of welfare in economics. In our setting, jobs are processed on restricted uniform parallel machines, where each machine has a speed and is only capable of processing a subset of jobs; a job's cost is its weighted completion time; and each machine sequences its jobs in weighted shortest processing time (WSPT) order. Whereas for the makespan social cost the price of anarchy is not bounded by a constant in most environments, we show that for our minsum social objective the price of anarchy is bounded above by a small constant, independent of the instance. Specifically, we show that the price of anarchy is exactly 2 for the class of unit jobs, unit speed instances where the finite processing time values define the edge set of a forest with the machines as nodes. For the general case of mixed job strategies and restricted uniform machines, we prove that the price of anarchy equals 4. From a classical machine scheduling perspective, our results establish the same constant performance guarantees for WSPT list scheduling. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Iterative coloring extension of a maximum clique

In this paper we present an improved branch and bound algorithm for the vertex coloring problem. The idea is to try to extend the coloring of a maximum clique to its adjacent vertices. If this succeeds, its successive neighbors are considered; in case of failure (i.e., in the case the initial colors are not sufficient), working on the subgraph induced by the maximum clique and its neighborhood, the lower bound is improved by seeking for an optimal coloring of this subgraph by branch and bound. The process is repeated iteratively until the whole graph is examined. The iterative scheme exploits a further lower bound obtained by integrating a simple algorithm into the maximum clique search, and a new method to compute upper bounds on subgraphs. Furthermore, a new branching rule and a method for the selection of the initial maximum clique are presented. Extensive computational results and comparisons with existing exact coloring algorithms on random graphs and benchmarks are given. © 2001 John Wiley & Sons, Inc. Naval Research Logistic 48: 518–550, 2001